package a_doubleWrite;

import java.util.Arrays;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-01 19:31
 */
public class L238 {
    //    space：n^2
//    public int[] productExceptSelf(int[] nums) {
//        int[][] dp = new int[nums.length + 2][nums.length + 2];
//        dp[1][0] = 1;
//        dp[nums.length + 1][nums.length] = 1;
//        for (int j = 1; j <= nums.length; j++) {
//            dp[1][j] = dp[1][j - 1] * nums[j - 1];
//        }
//        for (int i = nums.length; i > 0; i--) {
//            dp[i][nums.length] = dp[i + 1][nums.length] * nums[i - 1];
//        }
//        int[] ans = new int[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            ans[i] = dp[1][i] * dp[i + 2][nums.length];
//        }
//        return ans;
//    }
    public int[] productExceptSelf(int[] nums) {
        int[] ans=new int[nums.length];
        int left=1;//num[i]位置左边之和，
        int right=1;
        for (int i = 0; i <nums.length ; i++) {
            ans[i]=left;
            left*=nums[i];//乘积在下一次循环赋值
        }
        for (int i = nums.length-1; i >0 ; i--) {
            right*=nums[i];
            ans[i-1]*=right;
        }
        return ans;
    }

    public static void main(String[] args) {
        L238 l238 = new L238();
        int[] ints = l238.productExceptSelf(new int[]{1, 2, 3, 4});
        System.out.println(Arrays.toString(ints));
    }
}
